package algorithm;

import java.util.ArrayDeque;

/**
 * create by yongli on 2021-03-05 20:54
 */

class Solution {
    public int[] maxInWindows(int[] nums, int k) {
        int len = nums.length;

        int[] res = new int[len - k + 1];
        // 使用双端队列
        ArrayDeque<Integer> que = new ArrayDeque<>();
        for (int i = 0; i < k; i++) {
            while (que.size() > 0) {
                int el = que.peekFirst();
                if (nums[i] <= el) {
                    que.addFirst(nums[i]);
                    break;
                } else {
                    que.removeFirst();
                }
            }
            if (que.size() == 0) {
                que.addFirst(nums[i]);
            }
        }
        res[0] = que.peekLast();
        for (int i = 1; i < len - k + 1; i++) {
            while (que.size() > 0) {
                int el = que.peekFirst();
                if (nums[i] <= el) {
                    que.addFirst(nums[i]);
                    if (que.size() == k + 1) {
                        que.removeLast();
                    }
                    break;
                } else {
                    que.removeFirst();
                }
                if (que.size() == 0) {
                    que.addFirst(nums[i + k]);
                }
                res[i] = que.peekLast();
            }
        }

        return res;
    }
}